from string import whitespace
import re
import random


class Cell:
    def __init__(self, rowNum, colNum):
        self.rowNum = rowNum
        self.colNum = colNum
        self.boxNum = rowNum // 3 * 3 + colNum // 3
        self.cellNum = rowNum % 3 * 3 + colNum % 3
        self.value = 0
        self.cands = set()
        self.given = False

    def __str__(self):
        s = f"r{self.rowNum}c{self.colNum}"
        if self.value != 0:
            s += f"v{self.value}"
        else:
            s += "c"
            for c in self.cands:
                s += f"{c}"
        return s

    def str_value(self):
        return f"{self.value}"

    def str_cands(self):
        s = []
        for c in self.cands:
            s.append(str(c))
        s.sort()
        return "".join(s)

    def digits(self):
        if self.value != 0:
            return self.str_value()
        else:
            return self.str_cands()


class Grid:
    def __init__(self):
        self.rows = [
            [Cell(rowNum, colNum) for colNum in range(9)] for rowNum in range(9)
        ]
        self.solvedCount = 0

    def toZero(self):
        self.solvedCount = 0
        for rowNum in range(9):
            for colNum in range(9):
                self.rows[rowNum][colNum].value = 0
                self.rows[rowNum][colNum].cands = set(range(1, 10))
                self.rows[rowNum][colNum].given = False

    def copy(self):
        g = Grid()
        for rowNum in range(9):
            for colNum in range(9):
                g.rows[rowNum][colNum].value = self.rows[rowNum][colNum].value
                g.rows[rowNum][colNum].cands = self.rows[rowNum][colNum].cands.copy()
                g.rows[rowNum][colNum].given = self.rows[rowNum][colNum].given
        g.init()
        return g

    def __str__(self):
        s = ""
        for row in self.rows:
            for cell in row:
                s += str(cell.value)

    def init(self):
        self.cols = []
        self.boxes = []
        for colNum in range(9):
            self.cols.append([])
            for rowNum in range(9):
                self.cols[colNum].append(self.rows[rowNum][colNum])
        for boxNum in range(9):
            self.boxes.append([])
            for cellNum in range(9):
                rowNum = boxNum // 3 * 3 + cellNum // 3
                colNum = boxNum % 3 * 3 + cellNum % 3
                self.boxes[boxNum].append(self.rows[rowNum][colNum])

    def clearup(self):
        for row in self.rows:
            for cell in row:
                if cell.value != 0:
                    self.clearupHouse(self.rows[cell.rowNum], cell)
                    self.clearupHouse(self.cols[cell.colNum], cell)
                    self.clearupHouse(self.boxes[cell.boxNum], cell)

    def clearupHouse(self, house, solvedCell):
        reCells = []
        for cell in house:
            if cell.value != 0 or cell == solvedCell:
                continue
            if solvedCell.value in cell.cands:
                cell.cands.remove(solvedCell.value)
                reCells.append(cell)
        return reCells

    def solveOne(self, rowNum, colNum, value):
        cell = self.rows[rowNum][colNum]
        if cell.value != 0:
            return []
        if value not in cell.cands:
            return []
        cell.value = value
        cell.cands = set()
        self.solvedCount += 1
        rmCells = []
        rmCells += self.clearupHouse(self.rows[cell.rowNum], cell)
        rmCells += self.clearupHouse(self.cols[cell.colNum], cell)
        rmCells += self.clearupHouse(self.boxes[cell.boxNum], cell)
        return rmCells

    def removeCand(self, rowNum, colNum, cand):
        cell = self.rows[rowNum][colNum]
        if cell.value != 0:
            return False
        if cand not in cell.cands:
            return False
        if len(cell.cands) == 1:
            return False
        cell.cands.remove(cand)
        return True

    def input(self, s):
        pos = 0
        clean = [
            0,
        ] * 81
        for c in s:
            if c >= "0" and c <= "9":
                clean[pos] = int(c)
                pos += 1
            if c == ".":
                clean[pos] = 0
                pos += 1
            if pos == 81:
                break

        for rowNum in range(9):
            for colNum in range(9):
                cell = self.rows[rowNum][colNum]
                cell.value = clean[rowNum * 9 + colNum]
                if cell.value != 0:
                    cell.given = True
                    self.solvedCount += 1
                    self.cands = set()
                else:
                    cell.given = False
                    cell.cands = set(range(1, 10))

    def decode(self, s):
        pattern = r"(\.|\d|\{\d\}|\[\d+\]|\(\d\))"
        p = re.compile(pattern)
        cs = p.findall(s)
        if len(cs) > 81:
            cs = cs[:81]
        elif len(cs) < 81:
            cs = cs + ["."] * (81 - len(cs))
        rowNum = 0
        colNum = 0

        for c in cs:
            cell = self.rows[rowNum][colNum]
            if c == ".":
                cell.value = 0
                cell.cands = set(range(1, 10))
                cell.given = False
            elif c == "0":
                cell.value = 0
                cell.cands = set(range(1, 10))
                cell.given = False
            elif "1" <= c and c <= "9":
                cell.value = int(c)
                cell.cands = set()
                cell.given = True
                self.solvedCount += 1
            elif c[0] == "{":
                cell.value = int(c[1])
                cell.cands = set()
                cell.given = True
                self.solvedCount += 1
            elif c[0] == "(":
                cell.value = int(c[1])
                cell.cands = set()
                cell.given = False
                self.solvedCount += 1
            elif c[0] == "[":
                cell.value = 0
                cell.cands = set([int(x) for x in c[1:-1]])
                cell.given = False
            else:
                pass

            colNum += 1
            if colNum == 9:
                rowNum += 1
                colNum = 0
        # self.init()
        return True

    def encode(self):
        s = []
        for row in self.rows:
            for cell in row:
                # print(cell.given, cell.value, cell.rowNum, cell.colNum)
                if cell.value != 0:
                    if cell.given:
                        s.append(str(cell.value))
                    else:
                        s.append(f"({cell.value})")
                else:
                    s.append(f"[{cell.digits()}]")
        return "".join(s)

    def formatEncode(self):
        s = []
        for i, row in enumerate(self.rows):
            for j, cell in enumerate(row):
                if cell.value != 0:
                    if cell.given:
                        s.append(str(cell.value))
                    else:
                        s.append(f"({cell.value})")
                else:
                    s.append(f"[{cell.digits()}]")
                if j % 3 == 2:
                    s.append(" ")
            s.append("\n")
            if i % 3 == 2:
                s.append("\n")
        return "".join(s)

    def output(self):
        s = []
        for i, row in enumerate(self.rows):
            for j, cell in enumerate(row):
                if cell.value != 0:
                    s.append(f"{cell.value}")
                else:
                    s.append(f"0")
                if j % 3 == 2:
                    s.append(" ")
            s.append("\n")
            if i % 3 == 2:
                s.append("\n")
        return "".join(s)

    def printGrid(self):
        for i, row in enumerate(self.rows):
            for j, cell in enumerate(row):
                print(cell.value, end="")
                if (j + 1) % 3 == 0:
                    print(" ", end="")
            print()
            if (i + 1) % 3 == 0:
                print()

    def printList(self):
        for i, row in enumerate(self.rows):
            for j, cell in enumerate(row):
                if cell.value != 0:
                    print(cell.str_value(), end=" ")
                else:
                    print(cell.str_cands(), end=" ")
                if (j + 1) % 3 == 0:
                    print("\t", end="")
            print()
            if (i + 1) % 3 == 0:
                print()

    def validate(self):
        if self.solvedCount != 81:
            return False
        for row in self.rows:
            for cell in row:
                if cell.value == 0:
                    return False
        for i in range(9):
            if not self.validateHouse(self.rows[i]):
                print(f"error: row {i}")
                return False
            if not self.validateHouse(self.cols[i]):
                print(f"error: col {i}")
                return False
            if not self.validateHouse(self.boxes[i]):
                print(f"error: box {i}")
                return False
        return True

    def validateHouse(self, house):
        values = set()
        for cell in house:
            if cell.value < 1 or cell.value > 9:
                return False
            if cell.value in values:
                return False
            values.add(cell.value)
        return True

    def transpose(self):
        rows = [[Cell(rowNum, colNum) for colNum in range(9)] for rowNum in range(9)]

        for rowNum in range(9):
            for colNum in range(9):
                rows[rowNum][colNum].value = self.rows[colNum][rowNum].value
                rows[rowNum][colNum].cands = self.rows[colNum][rowNum].cands
                rows[rowNum][colNum].given = self.rows[colNum][rowNum].given
                rows[rowNum][colNum].rowNum = rowNum
                rows[rowNum][colNum].colNum = colNum

        self.rows = rows
        self.init()
        self.clearup()

    def rotate(self):
        # 创建新的9x9网格结构，初始化每个单元格的行列位置为旋转后的目标位置
        new_rows = [
            [Cell(row_num, col_num) for col_num in range(9)] for row_num in range(9)
        ]

        # 遍历原网格的每个单元格，复制属性到旋转后的新位置
        for original_row in range(9):
            for original_col in range(9):
                original_cell = self.rows[original_row][original_col]
                # 顺时针旋转90度的位置映射规则：(原行, 原列) → (原列, 8-原行)
                new_row = original_col
                new_col = 8 - original_row
                # 获取新位置的单元格并复制属性
                new_cell = new_rows[new_row][new_col]
                new_cell.value = original_cell.value
                new_cell.cands = original_cell.cands.copy()  # 深拷贝候选数集合
                new_cell.given = original_cell.given

        # 更新网格的行数据为旋转后的新数据
        self.rows = new_rows
        # 重新初始化列和宫数据（因为行数据已改变）
        self.init()
        # 清理候选数（根据已填写的数字更新相关行列宫的候选数）
        self.clearup()

    def upDown(self):
        # Swap rows in an upside-down manner
        new_rows = [
            [Cell(row_num, col_num) for col_num in range(9)] for row_num in range(9)
        ]
        for i in range(9):
            for j in range(9):
                new_cell = new_rows[8 - i][j]
                new_cell.value = self.rows[i][j].value
                new_cell.cands = self.rows[i][j].cands.copy()  # 深拷贝候选数集合
                new_cell.given = self.rows[i][j].given
        # Reinitialize columns and boxes after row transformation
        self.rows = new_rows

        self.init()
        # Update candidates based on the new grid configuration
        self.clearup()

    def leftRight(self):
        new_rows = [
            [Cell(row_num, col_num) for col_num in range(9)] for row_num in range(9)
        ]
        for i in range(9):
            for j in range(9):
                new_cell = new_rows[i][8 - j]
                new_cell.value = self.rows[i][j].value
                new_cell.cands = self.rows[i][j].cands.copy()  # 深拷贝候选数集合
                new_cell.given = self.rows[i][j].given
        # Reinitialize columns and boxes after row transformation
        self.rows = new_rows

        self.init()
        # Update candidates based on the new grid configuration
        self.clearup()

    def shuffle(self):
        # 生成1-9的随机排列（如[5,4,3,6,7,9,1,2,8]）
        permutation = list(range(1, 10))
        random.shuffle(permutation)

        # 遍历所有单元格进行数字置换
        for row in self.rows:
            for cell in row:
                # 替换已填写的数字（非0时）
                if cell.value != 0:
                    cell.value = permutation[
                        cell.value - 1
                    ]  # 原数字1对应permutation[0]

                # 替换候选数集合（处理1-9的候选）
                new_candidates = set()
                for candidate in cell.cands:
                    new_candidates.add(
                        permutation[candidate - 1]
                    )  # 候选数1对应permutation[0]
                cell.cands = new_candidates

        # 清理候选数以确保数独规则有效
        self.clearup()


if __name__ == "__main__":

    def main():
        g = Grid()
        s = "010743008030008071008000036705200000040010080000007605850000100420600090600831020"
        g.input(s)
        g.init()
        g.clearup()
        print(g.encode())

    def testDecode():
        s = """
        [29]1(6)743[29](5)8[259]3[249][59][2569]8[249]71[259][79]8[159][259][259][249]367[689]52[689][469][349][14][349][239]4[239][359]1[569][2379]8[2379][1239][89][1239][349][89]76[14]585[379][49][279][249]1[46][347]42[137]6[57][5][3578]9[37]6[79][79]831[457]2[47]
        """

        g = Grid()
        g.decode(s)
        print(g.encode())

    def rotate90():
        s = """
            [247]3[2467] 8[467](5) [279]1[479] 
            [2478]95 [1237][1347][12347] [237][248]6 
            1[248][24678] [2367]9[2347] [237]5[3478] 

            [245][245][249] [1359]86 [12359]7[1359] 
            (6)[258]3 [1579][17][179] 4[289][1589] 
            [578]1[789] 42[39] (6)[89][3589] 

            [348]6[148] [1379]5[13479] [179][49]2 
            9[245][124] [1267][1467][1247] 83[1457] 
            [2345]7[124] [1239][134]8 [159]6[1459] 

        """
        g = Grid()
        g.decode(s)
        g.init()
        g.clearup()
        g.rotate()
        print(g.encode())

    # testDecode()
    rotate90()
    # main()
